package com.fanshuai.algorithms.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * 烧饼排序是个很有意思的实际问题：
 * 假设盘子上有 n 块面积大小不一的烧饼，你如何用一把锅铲进行若干次翻转，让这些烧饼的大小有序（小的在上，大的在下）？
 *
 * 翻转有限制：只能翻转最上面的若干烧饼。烧饼用int[]数组表示，最上面的烧饼为a[0], 最底下烧饼为a[a.length - 1]
 *
 *
 */
public class CakeSort {

    /**
     * 给定数组A，进行烧饼翻转，选择一些正整数k<=a.length，然后进行若干次翻转，使得数组有序。输出k序列
     * @param a
     */
    public static List<Integer> cakeSort(int[] a) {
        List<Integer> kList = new ArrayList<>();
        cakeSort(a, a.length - 1, kList);
        return kList;
    }

    /**
     * 递归解法：
     * （1）找到0-n范围内最大的烧饼索引index，翻转0-index使得最大的烧饼到最上层
     * （2）翻转0-n使得最大的烧饼到最底层
     * （3）递归操作
     * @param a
     * @param n
     */
    private static void cakeSort(int[] a, int n, List<Integer> kList) {
        if (n == 0) {
            return;
        }
        int i = findMax(a, n);
        reverse(a, i);
        kList.add(i + 1); //记录翻转步骤
        reverse(a, n);
        kList.add(n + 1); //记录翻转步骤

        cakeSort(a, n - 1, kList);
    }

    private static int findMax(int[] a, int n) {
        int max = Integer.MIN_VALUE;
        int k = 0;
        for (int i = 0; i <= n; i++) {
            if (a[i] > max) {
                max = a[i];
                k = i;
            }
        }

        return k;
    }

    /**
     * 翻转烧饼操作，只能翻转最上面的烧饼，因此翻转index为0-i的烧饼
     * @param a
     * @param i
     */
    private static void reverse(int[] a, int i) {
        int left = 0, right = i;
        while (left < right) {
            int temp = a[left];
            a[left] = a[right];
            a[right] = temp;

            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 3, 2, 4, 12, 6, 4, 34, 21, 13, 51, 24};
        List<Integer> k = cakeSort(a);
        System.out.println(k);

        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
}
